#include <stdlib.h>
#include <stdio.h>
// 自己定义需要的栈结构，及栈基本操作函数，假设操作数都是整数
struct stack
{
    int data;
    struct stack * next;
    struct stack * pre;
};
/*在此定义并完成第一关函数，参考main要求*/
typedef struct stack *Stack;

Stack createNullStack()
{
    Stack top = (Stack)malloc(sizeof(struct stack));
    if (NULL == top) {
        printf("Out of Space!\n");
        return NULL;
    }
    top->data = 0;
    top->next = top;
    top->pre = top;
    return top;
}

void push(Stack s, int x)
{
    if (NULL == s)
        return;
    Stack p = (Stack)malloc(sizeof(struct stack));
    if (NULL == p) {
        printf("Out of Space!\n");
        return;
    }
    p->data = x;
    s->next->pre = p; 
    p->pre = s; 
    p->next = s->next;
    s->next = p;
}

int pop(Stack s)
{
    if (NULL == s || s == s->next)
        return 0;
    Stack p = s->next;
    int data = p->data;
    s->next->next->pre = s;
    s->next = s->next->next;
    free(p);
    p = NULL;
    return data;
}

void push_rev(Stack s, int x)
{
    if (NULL == s)
        return;
    Stack p = (Stack)malloc(sizeof(struct stack));
    if (NULL == p) {
        printf("Out of Space!\n");
        return;
    }
    p->data = x;
    s->pre->next = p; 
    p->next = s; 
    p->pre = s->pre;
    s->pre = p;
}

int pop_rev(Stack s)
{
    if (NULL == s || s == s->pre)
        return 0;
    Stack p = s->pre;
    int data = p->data;
    s->pre->pre->next = s;
    s->pre = s->pre->pre;
    free(p);
    p = NULL;
    return data;
}

int top(Stack s) {
    if (NULL == s || s == s->next)
        return 0;
    return s->next->data;
}
/* 火车从始发站（称为第1站）开出，在始发站上车的人数为a，然后到达第2站，在第2站有人上、下车，但上、下车的人数相同，
 * 因此在第2站开出时（即在到达第3站之前）车上的人数保持为a人。从第3站起（包括第3站）上、下车的人数有一定规律：
 * 上车的人数都是上两站上车人数之和，而下车人数等于上一站上车人数，一直到终点站的前一站（第n-1站），都满足此规律。
 * 现给出的条件是：共有n个车站，始发站上车的人数为a，最后一站下车的人数是m（全部下车）。
 * 试问x站开出时车上的人数是多少？
 * 本关任务：使用栈将递归函数转化为非递归函数。*/

int result(int n, int m, int a, int x) {
//    int i, a2, r, x_c_a, x_c_a2;  // 设x站下车人数x_c_a * a + x_c_a2 * a2
//    int b = 0, f = 1, num = a;
//    int c_a = 1, c_a2 = 0;  // 设第n-1站下车的人数为c_a * a + c_a2 * a2
//    for (i = 2; i < n - 1; ++i) {
//        r = b + f;
//        // c_a2总比c_a落后一个斐波那契数列, c_a和c_a2是斐波那契和的形式
//        c_a += f;
//        c_a2 += b;
//        b = f;
//        f = r;
//        if (i == x - 1) {
//            x_c_a = c_a;
//            x_c_a2 = c_a2;
//        }
//    }
//    a2 = (m - c_a * a)/c_a2; // n-1站求a2
//    num = x_c_a * a + x_c_a2 * a2; // 求出a2之后代入第n站
//    return num;
    // 设第一站上车人数为1*a+0*a2,第二站上车的人数为1×a+1*a2,
    // 然后下一站的上车人数等于前一站的上车人数加本站的人数,
    // 最后一站下车人数等于n-1站总人数,而n-1站总人数等于n-2站总人数+
    // 上车人数以斐波那契数列前n项和为系数的规律c_a * a + c_a2 * a2,c_a: 1 1 2 3 ...;c_a2:0 0 0 1 2 4 ...
    int i, j, a2, r, x_c_a, x_c_a2;  // 设x站下车人数x_c_a * a + x_c_a2 * a2
    int b = 0, f = 1, num = a;
    int c_a = 1, c_a2 = 0; // 设第二站下车的人数为a+a2,第n-1站下车的人数为c_a * a + c_a2 * a2 , c_a 比c_a2领先1个斐波那契数
    Stack fib = createNullStack();
    for (i = n - 2; i >= 0; --i) {
        if (i == 0) {
            push(fib, 0);
        } else if (i == 1) {
            push(fib, 1);
        } else {
            push(fib, -1); // 给未知数预留位置
        }
    }
    for (j = 3; fib->next->next->next != fib; ++j) {
        c_a2 += top(fib);
        fib->next->next->data = pop(fib) + top(fib);
        c_a += top(fib);
        if (j == x) {
            x_c_a = c_a;
            x_c_a2 = c_a2;
        }
    }
    a2 = (m - c_a * a) / c_a2;
    num = x_c_a * a + x_c_a2 * a2;
    return num;
}

/*
   第二关
   函数名：inToPost，本函数名和参数不能更改
   函数功能：将中缀表达式转换为后缀表达式输出 
   函数参数：中缀表达式，放在字符数组中 
   返回值：返回放有后缀表达式的栈 
*/
Stack  inToPost(char *expression)
{
   //在此处填写代码，完成中缀表达式转换为后缀表达式并输出
   /**********  Begin  **********/
    Stack s = createNullStack();
    Stack post = createNullStack();
    int num = 0;
    for (int i = 0; expression[i] != '\0'; ++i) {
        if (expression[i] >= '0' &&  expression[i] <= '9') {
            num = 0;
            do {
                num = num * 10 + expression[i] - '0';
                i++;
            } while (expression[i] >= '0' &&  expression[i] <= '9');
            push_rev(post, num+256);
            i--;
        } else if ('+' == expression[i] || '-' == expression[i]) {
            while(s != s->next && top(s) !='(')
                push_rev(post, pop_rev(s));
            push_rev(s, expression[i]);
        } else if ('*' == expression[i] || '/' == expression[i]) {
            push_rev(s, expression[i]);
        } else if ('(' == expression[i]) {
            push_rev(s, expression[i]);
        } else if (')' == expression[i]) { 
            while (top(s) != '(') {
                push_rev(post, pop_rev(s));
            }
            pop_rev(s);
        }

    }
    while (s != s->next) {
        push_rev(post, pop_rev(s));
    }
return post;
   /**********  End  **********/
}

//print函数用于输出后缀表达式，参数是 inToPost的返回值

void print(Stack s)
{
    while (s != s->next) {
        switch (top(s)) {
            case '+':
            case '-':
            case '*':
            case '/':
                printf("%c ", pop(s));
                break;
            default:
                printf("%d ", pop(s)-256);
        }
    }

}

/*
   第三关
   函数名：calExp，本函数名和参数不能更改
   函数功能：调用inToPost函数求解后缀表达式，并求解后缀表达式的值返回 
   函数参数： 
   返回值：无 
*/
int calExp(char *express)
{
   //在此处填写代码，完成表达式求值并输出
   /**********  Begin  **********/
    Stack s = inToPost(express);
    Stack operand = createNullStack();
    int op1, op2;
    while (s != s->next) {

        switch (top(s)) {
            case '+':
                op2 = pop(operand);
                op1 = pop(operand);
                push(operand, op1+op2);
                pop(s);
                break;
            case '-':
                op2 = pop(operand);
                op1 = pop(operand);
                push(operand, op1-op2);
                pop(s);
                break;
            case '*':
                op2 = pop(operand);
                op1 = pop(operand);
                push(operand, op1*op2);
                pop(s);
                break;
            case '/':
                op2 = pop(operand);
                op1 = pop(operand);
                push(operand, op1/op2);
                pop(s);
                break;
            default:
                push(operand, pop(s)-256);
        }
    }
    return  top(operand);
   /**********  End  **********/
}
